package someTestExcemple.huaweiOd.unionFindSet;

import java.util.Scanner;

//华为OD机试 - 开心消消乐 - 并查集（Java 2024 B卷 100分）
//将题目中的“点击一个1及其周围8个方向的1都反转为0”的操作理解为：
//将矩阵中相互连接（8个方向相邻）的1组成的一个连通块“一次性清除”。
// 因此，问题就转化为统计矩阵中有多少个这样的连通块，每个连通块只需要一次点击。
//基本类似与BroadCast 服务器广播这道题
public class HappyMirabilia {
    private static int[][] direction = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[][] arr = new int [n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        sc.close();
/*        使用双重循环遍历整个矩阵，对于每个位置：

        如果当前位置的值为0，则跳过；
        如果当前位置的值为1，说明找到了一个未处理的连通块，需要进行一次深度优先搜索（DFS）来将这个连通块中的所有1都“清除”（即标记为0）。
        当遇到1时，从该位置开始进行DFS：

        将当前位置的1标记为0，表示已处理；
        访问当前位置8个方向上的所有相邻位置（包括上下左右及4个对角线方向），如果相邻位置也是1，则递归地对该位置执行相同的操作，直到将当前连通块中所有的1都清除。
        每次DFS调用完成后，就代表成功“点击”并清除了一个完整的连通块。*/
        int count=0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(arr[i][j] == 1) {
                    dfs(i,j,arr,n,m);
                    count++;
                }
            }
        }
        System.out.println(count);

    }
    public static void dfs(int x,int y,int[][] arr,int n,int m) {
        //表示已经访问过
        arr[x][y] =0;
        for(int i=0;i<direction.length;i++) {
            int tx = x+direction[i][0];
            int ty = y+direction[i][1];
            if(tx>=0 && tx<n && ty>=0 && ty<m && arr[tx][ty] ==1) {
                dfs(tx,ty,arr,n,m);
            }
        }
    }
}
